package 二叉树;

public class 二叉树 {
	public static void main(String[] args) {
		
	    /**
	     * 构建二叉树
	     *         A
	     *       /  \
	     *      B    C
	     *     / \  /
	     *    D  E F
	     */
		BinaryTree tree = new BinaryTree();
		TreeNode node1 = new TreeNode(1, "A");
		TreeNode node2 = new TreeNode(2, "B");
		TreeNode node3 = new TreeNode(3, "C");
		TreeNode node4 = new TreeNode(4, "D");
		TreeNode node5 = new TreeNode(5, "E");
		TreeNode node6 = new TreeNode(6, "F");
		node1.left = node2;
		node1.right = node3;
		node2.left = node4;
		node2.right = node5;
		node3.left = node6;
		//设置根节点
		tree.setRoot(node1);
		//设置根节点，方法二
		//TreeNode root = node1;
		//tree.setRoot(root);
		
		//遍历
//		//ABDECF
//		tree.preOrder(tree.root);
//		//DBEAFC
		tree.midOrder(tree.root);
//		//DEBFCA
//		tree.postOrder(tree.root);
		//结点中的方法遍历
//		tree.nodePreOrder();
		
		//查找
		//查找与遍历不同，查找写在了结点中，遍历写在了树中
//		TreeNode preSearch = tree.preOrderSearch("A");
//		System.out.println(preSearch);
//		TreeNode midSearch = tree.midOrderSearch("A");
//		System.out.println(midSearch);
//		TreeNode postSearch = tree.postOrderSearch("A");
//		System.out.println(postSearch);
		
		//删除
//		tree.preOrder(tree.root);
//		tree.delNode("B");
//		System.out.println("删除B结点");
//		tree.preOrder(tree.root);
		
	}
}


/**
 * 二叉树
 * @author PC
 */
class BinaryTree {
	//根节点
	public TreeNode root;
	public BinaryTree() {
		super();
	}
	//初始化根节点，设置哪个结点是根节点
	public void  setRoot(TreeNode root) {
		this.root = root;
	}

	/**
	 * 这个方法是结点中的方法，其他都是树中的方法
	 */
	public void nodePreOrder() {
		System.out.println("结点中的前序遍历...");
		if(root != null) {
			root.preOrder();
		}else {
			System.out.println("空树，无法遍历...");
		}
	}

	/**
	 * 前序遍历（中左右）
     * output:A-B-D-E-C-F
     * 另外一种写法，在TreeNode类中写方法，可以直接使用this.left.preOrder()
	 * @param root 参数是根节点
	 */
	public void preOrder(TreeNode root) {
		if(root == null) {
			return;
		}else {
			System.out.println(root.data);
			preOrder(root.left);
			preOrder(root.right);
		}
	}

	/**
	 * 中序遍历（左中右）
     * output:D-B-E-A-F-C
	 * @param root
	 */
	public void midOrder(TreeNode root) {
		if(root == null) {
			return;
		}else {
			midOrder(root.left);
			System.out.println(root.data);
			midOrder(root.right);
		}
	}
	
	/**
	 * 后序遍历（左右中）
     * output:D-E-B-F-C-A
	 * @param root
	 */
	public void postOrder(TreeNode root) {
		if(root == null) {
			return;
		}else {
			postOrder(root.left);
			postOrder(root.right);
			System.out.println(root.data);
		}
	}

	/**
	 * 前序遍历查找，好像只能再结点中写方法，这里不能掉root.left.preOrderSearch()
	 * @param data
	 * @return
	 */
	public  TreeNode preOrderSearch(Object data) {
//		System.out.println("前序遍历查找...");
//		//判断当前结点是不是
//		if(root.data == data) {
//			return root;
//		}
//		//左子树遍历查找
//		//接受结果的结点resNode
//		TreeNode resNode = null;
//		if(root.left != null) {
//		}
//		return null;
		
		//使用
		if(root != null) {
			return root.preOrderSearch(data);
		}else {
			return null;
		}
	}
	
	/**
	 * 中序查找使用
	 * @param data
	 * @return
	 */
	public TreeNode midOrderSearch(Object data) {
		if(root != null) {
			return root.midOrderSearch(data);
		}else {
			return null;
		}
	}
	
	/**
	 * 后序查找使用
	 * @param data
	 * @return
	 */
	public TreeNode postOrderSearch(Object data) {
		if(root != null) {
			return root.postOrderSearch(data);
		}else {
			return null;
		}
	}
	
	/**
	 * 递归删除使用，需要先判断是否是root结点
	 * @param data
	 */
	public void delNode(Object data) {
		if(root != null) {
			//如果只有一个结点，需要判断是否是这个节点
			if(root.data == data) {
				root = null;
			}else {
				//不是，递归删除
				root.delNode(data);
			}
		}else {
			System.out.println("空树...");
		}
	}

	
}
/**
 * 结点
 * 注意：这里使用的都是public的属性，方便取值赋值
 * 注意泛型的使用，data是数据，不同于结点，它可以存放其他数据，而left和right都是 结点 
 * class TreeNode<T> {
		public int index;
		public T data;
		public TreeNode<T> left;
		public TreeNode<T> right;
 * @author PC
 *
 */

class TreeNode {
	public int index;
	public Object data;
	public TreeNode left;
	public TreeNode right;
	
	public TreeNode() {
		super();
	}
	public TreeNode(int index, Object data) {
		super();
		this.index = index;
		this.data = data;
	}
	@Override
	public String toString() {
		return "TreeNode [index=" + index + ", data=" + data + "]";
	}
	
	/**
	 * 前序遍历
	 */
	public void preOrder() {
		//输出根
		System.out.println(this);
		//左子树
		if(this.left != null) {
			this.left.preOrder();
		}
		//右子树
		if(this.right != null) {
			this.right.preOrder();
		}
	}
	
	/**
	 * 前序遍历查找
	 * @param data
	 * @return
	 */
	public TreeNode preOrderSearch(Object data) {
		System.out.println("前序遍历查找...");
		//判断是否当前结点
		if(this.data == data) {
			return this;
		}
		//左子树遍历查找
		//resNode用来存结果
		TreeNode resNode = null;
		if(this.left != null) {
			resNode = this.left.preOrderSearch(data);
		}
		//找到了就返回，没找到就找右子树
		if(resNode != null) {
			return resNode;
		}
		//没找到就找右子树
		if(this.right != null) {
			resNode = this.right.preOrderSearch(data);
		}
		return resNode;
	}
	
	/**
	 * 中序遍历查找
	 * @param data
	 * @return
	 */
	public TreeNode midOrderSearch(Object data) {
		TreeNode resNode = null;
		if(this.left != null) {
			resNode = this.left.midOrderSearch(data);
		}
		if(resNode != null) {
			return resNode;
		}
		
		System.out.println("中序遍历查找...");
		if(this.data == data) {
			return this;
		}
		
		if(this.right != null) {
			resNode = this.right.midOrderSearch(data);
		}
		return resNode;
	}
	
	/**
	 * 后序遍历查找
	 * @param data
	 * @return
	 */
	public TreeNode postOrderSearch(Object data) {
		TreeNode resNode = null;
		if(this.left != null) {
			resNode = this.left.postOrderSearch(data);
		}
		if(resNode != null) {
			return resNode;
		}
		
		if(this.right != null) {
			resNode = this.right.postOrderSearch(data);
		}
		
		System.out.println("后序遍历查找...");
		if(this.data == data) {
			return this;
		}
		return resNode;
	}
	
	/**
	 * 递归删除结点
	 * @param data
	 */
	public void delNode(Object data) {
		//注意：一定要判断左子结点是否为空，否则空指针异常
		if(this.left != null && this.left.data == data) {
			this.left = null;
			return;
		}
		//判断右子结点
		if(this.right != null && this.right.data == data) {
			this.right = null;
			return;
		}
		//都不是，左递归
		if(this.left != null) {
			this.left.delNode(data);
		}
		//都不是，右递归
		if(this.right != null) {
			this.right.delNode(data);
		}
	}
	
}